1. Field of the Invention
The present invention relates to a Viterbi decoder and a storing and reading method, and more particularly, to a Viterbi decoder and a storing and reading method capable of effectively reducing the amount of memory used.
2. Description of the Prior Art
Maximum likelihood sequence estimation, or MLSE, has been widely used in a variety of digital decoders, where a Viterbi detector is one example of a circuit for detecting convolution codes based on MLSE. As those skilled in the art will recognize, a communication channel always includes additive white Gaussian noise (or AWGN), or other forms of interference, so that a communication system encodes data before transmission for decreasing detection errors after the data is received. For example, via application of a specific algorithm, a given amount of data is convoluted to include more data bits before transmission. As a result, the communication system can detect whether the received data is correct according to the algorithm, and can even correct erroneous bits in the data.
Please refer to FIG. 1, which is a functional block diagram of a conventional Viterbi decoder 10. The Viterbi decoder 10 includes a branch metric generator 102, an add-compare-select unit 104, a survival memory unit 106, a trace back unit 108 and a last in first out buffer 110. The branch metric generator 102 receives and converts a data sequence Data_seq into soft decision information, and outputs branch metrics to the add-compare-select unit 104 accordingly. The add-compare-select unit 104 generates path metrics and survivor metrics of all states according to the branch metrics, and writes the survivor metrics into the survival memory unit 106. The trace back unit 108 reads the survivor metrics stored in the survival memory unit 106 to trace back, and outputs decoded data to the last in first out buffer 110 after tracing back beyond a predefined path depth, i.e. a path is converged. The last in first out buffer 110 outputs first stored data last (i.e. an input order is in reverse to an output order) to generate a decoded data sequence Dec_seq.
For operations of the Viterbi decoder 10, please refer to FIG. 2, which is a schematic diagram of a conventional Trellis tree of Viterbi algorithm with four states S00, S01, S10, and S11. The Trellis tree in FIG. 2 includes four current states S00, S01, S10, and S11 corresponding to a data Data_x of the data sequence Data_seq, four previous states S00′, S01′, S10′, and S11′ corresponding to a previous data Data_x−1 of the data sequence Data_seq, and branches in-between. Each branch indicates a relation between each current state and each previous state when 1 or 0 is encoded. When the Viterbi decoder 10 receives the data Data_x, the branch metric generator 102 calculates branch metrics corresponding to each branch, and then the add-compare-select unit 104 determines a path metric and a survivor metric of each current state according to the branch metrics and a previous path metric accumulated by a plurality of previous branch metrics. The path metric of each current state is calculated as follows:PS00=min{(PS00′,+BS00′→S00),(PS01′,+BS01′→S00)}  (Eq. 1)PS10=min{(PS00′,+BS00′→S10),(PS01′,+BS01′→S10)}  (Eq. 2)PS01=min{(PS10′,+BS10′→S01),(PS11′,+BS11′→S01)}  (Eq. 3)PS11=min{(PS10′,+BS10′→S11),(PS11′,+BS11′→S11)}  (Eq. 4)
Please refer to FIG. 3, which is a schematic diagram of the add-compare-select unit 104 in FIG. 1. The add-compare-select unit 104 includes adders 302, 304, a comparator 306 and a multiplexer 308. The adders 302, 304 adds branch metrics BS00′→S00 and BS0′1′→S00 with path metrics PS00′ and PS01′ of previous states S00′ and S01′, respectively, to generate adding results Add1 and Add2. The comparator 306 outputs a survivor metric Sur to the multiplexer 308 according to the adding results Add1 and Add2, to reflect a comparing result. The multiplexer 308 selects to output the smaller of the adding results Add1 and Add2 as a path metric PS00 according to the survivor metric Sur. Similarly, calculating circuits for other path metrics have the same structure and operations of the circuit in FIG. 3, and are not narrated hereinafter. Noticeably, when a new data of the data sequence Data_seq is entered, states of a previous data becomes previous states of the new data and path metrics of current states are simultaneously updated.
For writing and reading operations of the Viterbi decoder 10, please refer to FIG. 4, which is a schematic diagram of writing and reading operations when the survival memory unit 106 in FIG. 1 performs sequential writing in the prior art. The survival memory unit 106 includes banks Bank_1˜Bank_4. The banks Bank_1˜Bank_4 further include columns Col_1˜Col_n, respectively. The columns Col_1˜Col_n store survivor metrics of each state corresponding to each data of the data sequence Data_seq, respectively. The add-compare-select unit 104 performs writing operations with writing banks wr. The trace back unit 108 performs reading operations with trace back banks tb and decoding banks dc, i.e. decoding after tracing back beyond a predefined path depth, which is a depth of two banks in FIG. 4. Since both tracing back and decoding are reading operations, a ratio of a writing speed to a reading speed is 1:3. As shown in FIG. 4, the prior art utilizes sequential writing, and thus the add-compare-select unit 104 performs writing operations first from a column Col_1 of bank Bank_1 to a column Col_n of the banks Bank_1, and goes to write a column Col_1 of the bank Bank_2 after writing the column Col_n of the banks Bank_1. The trace back unit 108 has to perform reading operations according to an order in reverse to the writing order, i.e. performing trace back operations first from a column Col_n of the bank Bank_4 to a column Col_1 of the bank Bank_4, and goes to trace back a column Col_n of the bank Bank_3 after tracing back the column Col_1 of the bank Bank_4, whereby decoding is started after tracing back beyond the predefined path depth.
Since the trace back unit 108 reads data according to the reading order in reverse to the writing order when performing tracing back and decoding operations, only one memory bank is utilized for writing operations, another memory bank is utilized for reading operations, and the remaining two memory banks are idle in every interval of a clock, causing low memory efficiency. Besides, in order to use less memory, memory may be divided into more banks to increase a ratio of a reading speed to a writing speed in the prior art, but path delay will be increased and more memory is required when memory is divided into too many banks. Thus, there is a need for improvement in the prior art.